package mo.leetcode_hot;

import java.util.*;

@SuppressWarnings("Duplicates")
public class L207 {

    private boolean valid = false;
    private List<List<Integer>> list = new ArrayList<>();

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        for (int i = 0; i < numCourses; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < prerequisites.length; i++) {
            list.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        int[] visited = new int[numCourses];
        for (int i = 0; i < numCourses && valid; i++) {
            if (visited[i] == 0) {
                dfs(i, visited);
            }

        }
        return valid;
    }

    private void dfs(int i, int[] visited) {
        visited[i] = 1;
        List<Integer> dep = list.get(i);
        for (int x : dep) {
            if (visited[x] == 0) {
                dfs(x, visited);
                if (!valid) {
                    return;
                }
            } else if (visited[x] == 1) {
                valid = false;
                return;
            }
        }
        visited[i] = 2;
    }


    public boolean canFinish2(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] in = new int[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            int[] pair = prerequisites[i];
            List<Integer> targets = graph.get(pair[1]);
            if (Objects.isNull(targets)) {
                targets = new ArrayList<>();
                targets.add(pair[0]);
                graph.put(pair[1], targets);
            } else {
                targets.add(pair[0]);
            }
            in[pair[0]]++;
        }
        Stack<Integer> queue = new Stack<>();
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0) {
                queue.push(i);
            }
        }
        while (!queue.isEmpty()) {
            Integer val = queue.pop();
            List<Integer> integers = graph.get(val);
            if (integers != null) {
                for (int de : integers) {
                    in[de]--;
                    if (in[de] == 0) {
                        queue.push(de);
                    }
                }
            }
        }

        for (int i = 0; i < numCourses; i++) {
            if (in[i] != 0) {
                return false;
            }
        }
        return true;
    }

}
